Giga Games 1/Giga Games.iso/net/vir_real/papers/norskog.5d

Text File | 1993-06-20 | 112.0 KB | 3,820 lines

                                  - 1 -












                           5D Reference Manual

                               Revision 0.1
                         Release date: 4/21/1991


          Copyright (c) 1991 by Lance Norskog, Santa Clara, USA









       1.  _I_n_t_r_o_d_u_c_t_i_o_n

       5D is a portable implementation of "virtual reality".  It
       implements a simple, extensible programming language for
       real-time 3D graphics interaction, and forms the basis of a
       cyberspace/hypermedia-oriented window system.

       1.1  _S_c_o_p_e__o_f__5_D

       5D only addresses the _h_a_r_d_w_a_r_e _c_o_n_t_r_o_l level of 5D.  It
       provides a pleasant programming language for creating custom
       user interfaces, and network protocols for user interaction.
       This system is intended first as a platform for
       experimentation in 5D user interface and network interaction
       betwixt decks in larger persistent worlds.

       1.2  _P_o_s_s_i_b_l_e__a_p_p_l_i_c_a_t_i_o_n_s

       5D is a Cyberspace building block.  It communicates data in
       the form of 5D programs.  The 5D language encoding is dense
       enough to download simple worlds in several minutes over
       commodity 9600 baud modems, or ISDN.  With the future
       inclusion of a 2D text rendering model, 5D could support
       hypertext applications at this bandwidth.  X.25's ability to
       support several simultaneous connections to separate phone
       numbers opens impressive groupware and cyberspace doors.











                                  - 2 -



       The reference application for low-end decks is MazeWar.
       Several players on an Ethernet, one to a deck, wander
       through a maze shooting at each other.  The decks
       continuously broadcast the position, eye direction, laser
       direction, and trigger status of their users.

       Scientific Visualization uses multi-dimensional viewing
       methods.  Ray-tracing systems often include "fog"
       implemented as 3D stochastic white-out blurring.  A 5D
       system could support sci-vis by implementing fog from a 3D
       dataset, thus allowing a surgeon to _e_x_p_e_r_i_e_n_c_e a brain scan
       instead of viewing it.  This will, of course, not run in
       real-time on a PC.

       The Habitat system [ref ??] uses standard computer game
       technology and telecommunications to implement Cyberspace
       with a real-time quasi-3D interface.  Every evening 300-400
       people sit at home with a Commodore 64 and a 300 baud modem
       playing an elaborate and permanent computer game with up to
       5 other subscribers in a room or "cell".  Habitat has 20,000
       cells total, and 15,000 paying subscribers.  It should be
       possible to implement a 5D version of the Habitat system at
       baud rates of 9600 on up.

       1.3  _5_D__G_l_o_s_s_a_r_y

       world               A "world" is a visible 3D scene with
                           which the user interacts.

       deck                A "deck" is the combination of visual,
                           sound, and force-feedback hardware that
                           implements a 5D environment for one or a
                           few users.

       program             On a network, a "program" is the remote
                           application which is responsible for a
                           world.

       World Manager       A World Manager is a remote program
                           responsible for the main operation of
                           the deck.  A typical deck is set up to
                           have more than one world available; the
                           WM allows switching between the
                           different worlds.

       TerraFormer         The TTTTeeeerrrrrrrraaaaFFFFoooorrrrmmmmeeeerrrr is a visual programming
                           CASE system for 5D trees.  It is a 5D
                           program which presents a tree as a 3D
                           scene, using translucent structure
                           blocks to display several levels of
                           structure simultaneously.











                                  - 3 -



       2.  _5_D__S_y_s_t_e_m__A_r_c_h_i_t_e_c_t_u_r_e

       5D runs on personal computers and professional workstations.
       It presents an interactive real-time 3D environment for the
       user to work with.  It may read in and present a "canned"
       world description from a file, or download one over a
       network connection.  The world description consists of
       picture elements (polygons, spheres, etc.)  which are drawn
       in 3D, and many other software constructs necessary to
       implement a complete free-running program inside the deck.
       Constructs include various 3D graphics mathematics
       operations, sound generation control, force feedback
       control, and network communications.

       5D is a real-time simulation system for 3D graphics scenes.
       A collection of objects exists, and exhibit various
       behaviors in response to external input.

       2.1  _L_a_n_g_u_a_g_e__D_e_s_i_g_n__P_h_i_l_o_s_o_p_h_y

       "_W_e _t_o_o_k _a _f_e_w _s_i_m_p_l_e _i_d_e_a_s _a_n_d _b_e_a_t _t_h_e_m _t_o _d_e_a_t_h."
       - _D_e_n_n_i_s _R_i_t_c_h_i_e _n_e_v_e_r _s_a_i_d _t_h_i_s _a_b_o_u_t _d_e_s_i_g_n_i_n_g _U_N_I_X.

       A real-time software system must veer in one of two opposing
       directions:

          +o it can allow the programmer complete control over the
            computer, and provide a range of services to a program,
            _o_r

          +o it can take over the low-level control of the computer
            and provide a set of high-level constructs which the
            programmer can arrange into a program.  The system then
            implements real-time response by "doing the best it
            can" based on the given constructs.

       5D chooses the latter method.  It is a simulation
       description language.  It includes a rich set of very
       abstract operators for describing 3D graphics scenes.  The
       point is to get as close as possible to letting the
       programmer say "_d_o _w_h_a_t _I _m_e_a_n".  A general principle is
       that the more abstract the language, the more efficient the
       compiled code IFF the language constructs are carefully
       designed for compilability.  The more the compiler
       understands what you're "really" doing, the better code it
       can generate.
















                                  - 4 -



       2.2  _C_o_n_t_r_o_l

       "_W_h_e_n _I _h_e_a_r _t_h_e _w_o_r_d _M_a_c _I _r_e_a_c_h _f_o_r _m_y _g_u_n."

       Since 5D is never saved in binary format, the user may alter
       any aspect of a world at any time.  User interfaces are
       generally designed by programmers, who are generally
       terrible at it.  5D users are not forced to operate canned
       software, but may change it at any time.  The user is in
       control, not the programmer.

       The 5D software community is encouraged to develop libraries
       of new software which can be disseminated as simple tools,
       not complete enclosed worlds.  A kinematics toolkit, for
       example, is badly needed for many applications.

       2.3  _C_l_e_a_n_l_i_n_e_s_s

       The language is defined by a small set of basic operators
       and data types, which are then combined to create useful
       programming constructs.  Parsimony is a virtue in language
       design.  _I_f _s_o_m_e_t_h_i_n_g _c_a_n _b_e _i_m_p_l_e_m_e_n_t_e_d _a_s _a _c_o_m_b_i_n_a_t_i_o_n _o_f
       _e_x_i_s_t_i_n_g _c_o_n_s_t_r_u_c_t_s, _i_t _w_i_l_l _n_o_t _b_e _d_e_f_i_n_e_d _a_s _a _s_e_p_a_r_a_t_e
       _b_u_i_l_t-_i_n _c_o_n_s_t_r_u_c_t.

       The primary motivation for this is that a system feature,
       once made available to the user community, is immortal.
       Mature systems generally have a thick layer of "barnacles",
       old features which don't slough off like dead skin.  These
       systems are much larger and more complex than they need to
       be because they must provide backwards compatibility for
       these "mistakes of youth".

       The 5D design process is a continuing search for simpler and
       more basic constructs.  The best analogy is to the physical
       world:  quarks are combined into protons, neutrons, and
       electrons, which are combined into many different molecules,
       which are ultimately combined into visible objects such as
       chairs.

       The X Window System, on the other hand, includes 1000
       different predefined molecules which don't fit together very
       well.  5D was designed with the X Window System as a shining
       example of poor design.


















                                  - 5 -



       3.  _L_a_n_g_u_a_g_e__C_o_n_c_e_p_t_s

       5D was motivated by the need for a very high-level
       programming language for implementing Virtual Reality
       software.  It is interpretable, compilable, malleable to
       parallel and custom graphics hardware configurations, and
       friendly (well, maybe) to non-programmers.

       3.1  _D_e_s_i_g_n__c_o_n_s_t_r_a_i_n_t_s

       5D has four major design constraints:

         1.  It is a programming language for designing worlds.

         2.  It is a protocol for interacting with an application.

         3.  It operates in real-time; i.e. the language constructs
             operate in a _p_r_e_d_i_c_t_a_b_l_e amount of time.

         4.  It is portable to the wide variety of the hardware
             platforms used in computer graphics.

       The search for clean, elegant solutions for the problems
       caused by these constraints is the source of most of the
       peculiar features of the language.

       3.2  _H_i_e_r_a_r_c_h_i_c_a_l__D_i_s_p_l_a_y__L_i_s_t_s

       5D was inspired by the _h_i_e_r_a_r_c_h_i_c_a_l _d_i_s_p_l_a_y _l_i_s_t.  In
       standard 3D modeling systems, a 3D scene description is
       traversed and rendered each time the scene or the viewpoint
       changes.  Abstract physical models are described as to their
       shape, color, shininess, etc. Separate copies or _i_n_s_t_a_n_c_e_s
       of these objects are then placed in 3-space.

       3.3  _I_n_h_e_r_i_t_a_n_c_e

       The objects _i_n_h_e_r_i_t their physical properties from their
       base descriptions, but an individual instance may change any
       of those properties.  Arranging these object definitions and
       instantiations into trees gives the benefits of data-hiding
       and modular software construction.  An object definition may
       include by reference other object descriptions, and may also
       change properties inherited from those object descriptions.
       Object instantiations grouped into a tree may inherit
       properties from the _p_a_r_e_n_t_s of the tree.  This is a very
       powerful technique for describing the graphics portion of a
       3D application; other techniques for data structuring can be
       layered atop it as interconnections between tree members.
       In PHIGS and other 3D modeling systems, these objects define
       a static scene, and consist solely of graphics primitives.











                                  - 6 -



       Virtual Reality also needs to describe dynamic changes in a
       world.  Games need to describe the physics of object
       collision, while molecular models must implement gradual
       force field interactions.  Many other standard programming
       facilities are needed also, such as communication protocols
       and I/O device drivers.

       3.4  _D_a_t_a_f_l_o_w__P_r_o_g_r_a_m_m_i_n_g

       5D extends the display list to a full programming language
       by using the paradigm of Dataflow Programming [ref ??].
       Dataflow languages express a complete program as a lattice
       of operations.  At the beginning of a computation, values
       enter the lattice of operations.  These values may be static
       constants, the current value of input devices, or the
       results of a previous computation.  At the end of
       computation, one or more values pop out of the "top" of the
       lattice; these are the results of the computation.

       A 5D "world" is a lattice.  This lattice is not evaluated in
       one computation.  Instead, individual sub-lattices direct
       the system when to evaluate them.  Sub-lattices draw on the
       screen, emit sound, send network messages, and operate
       force-feedback devices as side effects of their execution.

       3.4.1  _D_a_t_a_f_l_o_w__L_a_t_t_i_c_e__O_r_g_a_n_i_z_a_t_i_o_n
       Each node of the lattice has an operator, one or more
       super-nodes, zero or more subnodes, and zero or more
       properties.  For purposes of a simple language organization,
       lattices are organized into expression trees wherever
       possible.  The object definition system (see below) makes
       this feasible.

       3.5  _F_e_e_d_b_a_c_k

       5D objects can be connected in cyclic graphs.  This does not
       imply that the language can get into an endless loop!  The
       tree members are evaluated according to their frequency
       properties.  The value of a tree in a cyclic graph is
       eventually fed back into the next evaluation of that tree.
       Feedback is a natural method for implementing rhythmic
       objects and dynamics simulations; these are generally
       defined with differential equations in a feedback loop.

       3.6  _O_b_j_e_c_t__O_r_i_e_n_t_a_t_i_o_n

       5D is an object-oriented language.  The fundamental paradigm
       is object-oriented dataflow programming: a lattice, or
       directed acyclic graph, of arithmetic expressions feeds a
       set of software operations with numerical information.
       These operations may draw geometric objects, make sounds,











                                  - 7 -



       send messages over communications channels, or control
       force-feedback devices.

       Since these I/O devices must be controlled in real-time, 5D
       does not contain constructs which require an unpredictable
       amount of time to execute.  Whether this or that construct
       is "efficient" is irrelevant to real-time work;
       predictability is the issue.  Thus, very high-level language
       concepts like actors, object messaging, dynamic
       instantiation, etc. are not used.  The contents of the
       lattice is limited to operations of known execution time.
       Otherwise, the frame rate of the system would randomly vary
       from several frames per second to several seconds per frame.

       Objects are used as the organizing principle for defining
       the possible componenents of the lattice, and their possible
       interconnection.  There is a large built-in library of
       _p_r_i_m_i_t_i_v_e _c_l_a_s_s_e_s.  Programs may also define their own
       classes.  References to user-defined classes are _r_e_w_r_i_t_t_e_n
       according to their class definitions until the lattice is
       entirely in terms of the primitive classes.  The resulting
       lattice is incrementally compiled and executed repetitively.


       4.  _L_a_n_g_u_a_g_e__R_e_f_e_r_e_n_c_e

       5D uses an extremely simple language.  It is built on
       several elements:  objects, classes, properties, templates,
       trees, and IDs.  These language elements are used to
       describe rich, complex user interaction environments in a
       very dense format.

       4.1  _O_b_j_e_c_t_s__a_n_d__C_l_a_s_s_e_s

       An _o_b_j_e_c_t is an element of an interactive environment.  A
       _c_l_a_s_s is a generic description of a type of object.  Classes
       may be modified and combined to create new classes.  The
       original classes are called _p_a_r_e_n_t- or _s_u_p_e_r_c_l_a_s_s_e_s.  A deck
       starts off with many pre-defined _p_r_i_m_i_t_i_v_e _c_l_a_s_s_e_s.  A 5D
       program may include new class definitions which derive from
       the primitive ones.  A class may contain two or more objects
       from different parent classes.  This means that a class is
       always an extended or modified version of its parents.  It
       may add and delete operators and properties, possibly
       overriding definitions inherited from the parent classes.

       Objects are instances of their class definition.  Objects
       may be leaf nodes, or may be _c_o_n_s_t_r_u_c_t_e_d from objects of
       other classes.













                                  - 8 -



       4.1.1  _T_y_p_e_s
       Some classes are types, some are not.  _A_b_s_t_r_a_c_t _s_u_p_e_r_c_l_a_s_s_e_s
       are defined only so that child classes may be derived from
       them.  They are not useful for instancing objects, and thus
       do not allow this to occur.  Types are classes which may be
       used for instancing objects.

       4.2  _T_e_m_p_l_a_t_e_s

       A _t_e_m_p_l_a_t_e describes a space of possible 5D program trees.
       Templates are used several ways in 5D.  Most important,
       templates are used to describe the space of possible uses of
       an operator in a class definition.  This allows an operator
       definition to handle several different invocations.
       Templates are also used to verify a tree downloaded from a
       network connection; they supply a "syntax check" for
       accepted trees which can be used to decide whether to
       execute a downloaded tree.

       4.2.1  _T_e_m_p_l_a_t_e__s_y_n_t_a_x__[__p_r_o_p_o_s_e_d__]
       Template trees are separate type of tree node.  There are
       several forms of template node, defined by the _k_i_n_d=
       keyword.  Here are the values of the _k_i_n_d= keyword and the
       associated sub-tree formats:

       multi (X)           maps to 0 or more occurrences of the
                           tree node (X).

       order (X) (Y)       maps to the tree pair (X) (Y) or the
                           tree pair (Y) (X).

       sub (X)             maps to an arbitrary-shaped tree of
                           nodes described by (X).

       and (X) (Y)         maps to the boolean AND of the trees
                           described by (X) and (Y).

       or (X) (Y)          maps to the boolean OR of the trees
                           described by (X) and (Y).

       not (X)             maps to the boolean NOT of the tree
                           described by (X).

       Notes:
       The _o_r_d_e_r, _a_n_d, and _o_r nodes may contain two or more
       children.

       Templates are, by nature, underspecified.  A template
       without the _k_i_n_d keyword may use _t_y_p_e. A _t_y_p_e template may
       optionally use _v_a_l_u_e.  This template describes 0 or more
       Numbers:











                                  - 9 -



                (template kind=multi
                    (template type=Number))

       Tree templates may be used in combination. The template:
                (template kind=sub
                    (template kind=or
                        (template type=Void)
                        (template type=Number)))

       corresponds to one or more trees of algebraic expressions.
       Since the Number class does not operate on Voids, thus legal
       5D trees matching this template can be a one or more Number
       expressions hanging under a tree of Voids, or one Number
       expression with no Voids at all.
       Templates may be assigned IDs.

       A nodes of type Address may substitute at any place for any
       other node, if its referent node matches a template.  Nodes
       of type Address may also be specified in a template.
       [ Templates have proven the thorniest design task in 5D.
       I'm still not happy with the design. ]

       4.3  _P_r_o_p_e_r_t_i_e_s

       If objects are nouns, properties are adjectives.  Properties
       influence the nature of objects.  Drawable objects, as
       mentioned above, have colors and reflectivity.  Other
       objects have other properties:  sound channels, for example,
       have the property of volume.  The value of a property may be
       specified by a separate 5D program tree. The one restriction
       here is that no object used in the program tree may itself
       have properties.

       However, a property itself has a few attributes:

       Inheritance         The properties of a node may be
                           inherited automatically down the tree.
                           Every node of type X may use or set the
                           properties defined for class X.  An
                           inheritable property which is set at a
                           node overrides the inherited value of
                           those properties.  The new setting is
                           visible to all of its children of the
                           same type.

       Default             Every property description includes a
                           default value for a property.  If a
                           value is not specified or inherited for
                           that property, the default is used.













                                  - 10 -



       Writeability        A property may or may not be changed by
                           a node.  A read-only property may be set
                           at the top of a tree and then not reset
                           by its children.

       4.4  _T_r_e_e_s_,__L_a_t_t_i_c_e_s_,__a_n_d__C_y_c_l_i_c__G_r_a_p_h_s

       First, some basic Graph Theory:  a _g_r_a_p_h is a collection of
       nodes connected by edges.  A graph where the edges have a
       direction assigned to them is a _d_i_r_e_c_t_e_d _g_r_a_p_h.  A _t_r_e_e is a
       graph in which there are no loops at all.  A _l_a_t_t_i_c_e is a
       directed graph in which there are no loops at all.  Unlike a
       tree, a lattice may have two or more edges "pointing" at the
       same node.  A _d_i_r_e_c_t_e_d _c_y_c_l_i_c _g_r_a_p_h may have loops where the
       edges form a circle.

       In 5D a program is described by a directed graph which has
       aspects of a tree, a lattice, and a directed cyclic graph.
       A program is specified as a tree.  Each branch or leaf of
       the tree is called a _n_o_d_e.  Special _p_o_i_n_t_e_r _n_o_d_e_s may refer
       to other nodes, which may in fact be _p_a_r_e_n_t _n_o_d_e_s.  Thus,
       with pointer nodes the tree can become a lattice or even a
       cyclic graph.  [ Think of the UNIX file system with symbolic
       links. ]

       4.4.1  _P_r_o_p_e_r_t_y__I_n_h_e_r_i_t_a_n_c_e__v_i_a__p_o_i_n_t_e_r_s
       Properties are inherited statically, not dynamically.  When
       trees are executed via pointers, they still inherit their
       properties from their tree parent, not via pointing node.

       4.5  _I_D_s

       Any node in a 5D program tree may have a name attached to
       it.  This name must be unique within a subset of the tree.
       Names are assigned via the ID keyword.

       IDs is useful in several contexts.  Class definitions name
       themselves this way.  Variables named with IDs are used to
       transform the program tree into a lattice.  Certain IDs have
       special pre-defined meanings.

       4.6  _T_r_e_e__c_o_n_s_t_r_u_c_t_i_o_n_

       Each node of the tree is one of a few node types.  One or
       more keywords modify the node type.

       4.6.1  _N_o_d_e__t_y_p_e_s
       5D has several types of tree nodes:

       Class               indicates that the entire tree is a
                           class definition.  A class node must











                                  - 11 -



                           have the keywords IIIIDDDD and ssssuuuuppppeeeerrrr.

       Property            specifies a property of this node.  In a
                           class definition, a property node
                           defines a property which instances of
                           this class have.  In an object
                           instantiation, an property node sets a
                           property of this node.  A property node
                           must have the keywords IIIIDDDD and _t_y_p_e, and
                           must have a subtree containing the
                           default value of the property.

       Input               in a class definition specifies a
                           collection of superclass objects which
                           form this class.

       Data                in a class definition specifies a
                           collection of superclass objects which
                           are secret to an instantiation of this
                           class.

       Op                  specifies an operation node.  In a class
                           definition, an operation node and
                           subtree indicate a method the class
                           implements.  In an object instantiation,
                           an operation node invokes the
                           corresponding method in the class
                           definition.  An op node may have the
                           keywords IIIIDDDD and nnnnaaaammmmeeee.

       Template            specifies a variable-format tree.  A
                           template tree defines a space of
                           possible tree shapes.  It must have the
                           ffffoooorrrrmmmmaaaatttt keyword.

       Rewrite             specifies the replacement tree in a
                           method.

       Comment             is used for multi-line commentary.

       Set                 is the dataflow lattice connection
                           operation.  Set assigns the value of the
                           right-hand tree to the left-hand
                           nodename.

       4.6.2  _M_o_d_i_f_i_e_r_s
       5D has several basic modifiers:

       ID                  assigns a unique name to this node.  Any
                           node may have a name attached to it.
                           This name must be unique, subject to











                                  - 12 -



                           certain restrictions noted below in the
                           section "Scoping Rules".

       Super               indicates a superclass.  This is used
                           several ways in class definitions.  In
                           the class definition node, it names the
                           parent classes.  In the operator and
                           property definition nodes, it may be
                           used to refer to properties defined by
                           parent classes.

       Type                indicates the class of a property or
                           operation by naming the class definition
                           node.

       Name                indicates the name of the operation in
                           an operation node

       Value               indicates the actual value contained by
                           a leaf node.  A value is a number in
                           standard C decimal, octal, or hex
                           format.

       Format              defines the type of a template node in a
                           template subtree.

       Refer               means that this node is an indirect
                           node.  The value of the Refer keyword is
                           an ID.  This node receives its type and
                           value from the ID'd node.  This node may
                           also possess a Type keyword, which must
                           match the type of the ID'd node.  [ TTTThhhhiiiissss
                           iiiissss uuuuggggllllyyyy.... IIIItttt sssshhhhoooouuuulllldddd nnnnooootttt eeeexxxxiiiisssstttt....  CCCCllllaaaassssssss
                           AAAAddddddddrrrreeeessssssss hhhhaaaannnnddddlllleeeessss tttthhhhiiiissss....  EEEEiiiitttthhhheeeerrrr tttthhhhaaaatttt,,,, oooorrrr
                           ccccllllaaaassssssss AAAAddddddddrrrreeeessssssss sssshhhhoooouuuulllldddd nnnnooootttt eeeexxxxiiiisssstttt aaaannnndddd aaaallllllll
                           ppppooooiiiinnnntttteeeerrrrssss sssshhhhoooouuuulllldddd bbbbeeee ddddoooonnnneeee wwwwiiiitttthhhh RRRReeeeffffeeeerrrr.... ]

       IsType              is a boolean expression for whether or
                           not a class definition is a _t_y_p_e.  A
                           class definition which is not a type may
                           only be used as an abstract superclass,
                           it may not be used in a program.

       Inherited           is a boolean expression for whether or
                           not a property is inherited.  If it is
                           not, it must be explicitly specified in
                           each use of the object.

       Remove              deletes an inherited operator or
                           property from a class definition.












                                  - 13 -



       writeable           is a Boolean value in property
                           definitions.  If false, the property may
                           not be changed by its heirs or by the
                           "set properties" operator in the Void
                           object.

       Along with keywords, there may be arbitrary text surrounded
       by double quotes (").  These are comments and are ignored by
       the 5D interpreter.

       4.6.2.1  _C_o_m_m_e_n_t__c_o_n_v_e_n_t_i_o_n_s
       The 5D development system has several conventions for
       comments.  A comment beginning with the string "Summary:" is
       considered to be a short (one-line) summary of this tree
       node, and should be used in class, operator, and property
       definition nodes.  A comment beginning with the string
       "Treetype:" is a directive to the TTTTeeeerrrrrrrraaaaFFFFoooorrrrmmmmeeeerrrr that a tree is
       a specific type of database, such as a 3D model or a
       differential equation, and should be displayed or edited
       with a special application.

       4.7  _T_r_e_e__e_n_c_o_d_i_n_g

       There are two possible tree encodings, ascii & ASN.1 binary
       format.

       4.7.1  _A_s_c_i_i__F_o_r_m_a_t
       The 5D ASCII syntax is rudimentary, to say the least.  It is
       designed to be very quick to parse, both by a deck and by
       the TerraFormer.  It is in standard US 7-bit ASCII, with 8-
       bit and 16-bit text allowed in comments.  You may send it in
       e-mail, and control it with SCCS or RCS.  You're just not
       expected to read it, and you are strongly urged not to write
       it.

       A tree node is started by left parentheses (LP) and stopped
       by right parentheses (RP).  After the LP comes one of the
       above node type strings.  After the node type are zero or
       more keywords.  Some of the keywords may be of the form
       aaaaa=bbbbb.  These keywords are accepted by the node type
       keyword according to its wont.  After these keywords comes,
       you guessed it, another LP or an RP.  A series of RP's may
       be expressed by a right bracket (RB).  An RB substitutes for
       RP only if there can be nothing but the RP at that location.

       The exact syntax of the contents of data nodes is not final.
       Numbers are stored in the standard C "printf" floating point
       formats.  Images are stored in PBM format.  Sound samples
       are stored as a series of text numbers, unsigned.  Ascii
       text strings are not supported as data.  See section "Text".












                                  - 14 -



       4.7.2  _A_S_N_._1
       A 5D program is encoded as one large tree.  The node
       contains the type and whatever keywords are there as a data
       structure of strings.

       Existing source code from an SNMP agent which encodes and
       decodes a pre-defined ASN.1 grammar looks quite time-
       efficient.  Binary data is stored in the ASN.1 format in
       very compact formats.

       It may be necessary to process a received tree "on the fly"
       without storing the entire tree in source form.  The ASN.1
       format might work better in postfix format rather than the
       ASCII format's prefix format, Simple tree nodes are
       processed first, then knitted together.  The "incoming
       stack" maintains the database of processed trees which await
       the processing of their controlling nodes.

       4.7.3  _T_r_e_e__E_n_c_o_d_i_n_g__S_u_m_m_a_r_y
       The ASCII format is readable, and may be mailed and used
       under software control systems.  But, it is not very dense,
       and in particular uses very inefficient methods for storing
       binary data.  The ASCII format is used as a fluid medium for
       experiments in rearranging the 5D syntax.

       The ASCII format will be the dominant use in development,
       authoring, and workstation environments, but the broader
       network-based users will use ASN.1 almost exclusively
       because its an international standard and because of its
       space-efficiency.

       4.8  _C_l_a_s_s__d_e_f_i_n_i_t_i_o_n

       A class definition has up to five sections:

       Superclass          The superclasses used to derive this
                           class.

       Property            The properties used by the class.

       Data                Secret data objects used by a member of
                           this class.

       Input               Some classes are ordered lists of parent
                           objects.

       Method              The rewrite rules for the class.

       The Property, Data, and Input sections are optional.













                                  - 15 -



       4.8.1  _S_u_p_e_r_c_l_a_s_s__S_e_c_t_i_o_n
       The superclass section defines all the parent classes of a
       class.  The 5D class heirarchy is a lattice:  at the top is
       the class Object which effectively does nothing.  It is the
       only class with no superclass.  All other classes have one
       or more superclasses.  The properties and operators defined
       in the parent classes are automatically inherited by the
       class.

       4.8.2  _P_r_o_p_e_r_t_y__S_e_c_t_i_o_n
       The property section defines any properties which may affect
       the operation of this class.  For example, class Drawable
       contains 3D visible objects and thus has the properties of
       color, reflectivity, etc.  But, class Number has no
       properties:  "5 + 4" is always 9.

       4.8.3  _D_a_t_a__S_e_c_t_i_o_n
       The Data section defines secret data objects.  These are
       unique to each instantiation of a class, and may only be
       manipulated within the class definition.

       4.8.4  _I_n_p_u_t__S_e_c_t_i_o_n
       Classes which contain Input sections are "aggregations" or
       collections of objects.  For example, a Point is 3 Numbers.
       The Input section is optional.  Classes without Input
       sections may redefine the behavior of a parent class, or
       create a new class with behaviors of several parent classes.
       Operations on the members of the Input section are inherited
       _i_n _t_o_t_o:  see the definition of addition and subtraction on
       Complex numbers below.

       4.8.5  _M_e_t_h_o_d__s_e_c_t_i_o_n_s
       The Method sections give the substition rules for a class.
       A "method" handles a given operation on an object.  For
       example, class Number has a method `+' which handles adding
       two or more numbers.  Tree templates are used to describe
       possible invocations of an operator in the context of this
       type.  A second tree of object operations is substituted for
       the matched tree.  This second tree is called the _r_e_w_r_i_t_e
       rule, because operator invocations are _r_e_w_r_i_t_t_e_n.

       The template facility is a powerful context-sensitive device
       for describing the use of an object.  It describes the
       replacement expression tree for each operation that can be
       performed on the object.  For example, the operation
       Vertex_Normal on a Point is substituted with the appropriate
       mathematics on the constituent Numbers.

       When an object instance is evaluated, one of the methods in
       the object's tuple list is evaluated and its outputs are the
       outputs of the instance.  Which method? _T_h_e _o_n_e _w_h_o_s_e











                                  - 16 -



       _t_e_m_p_l_a_t_e _m_a_t_c_h_e_s _t_h_e _s_h_a_p_e _o_f _t_h_e _t_r_e_e _s_u_r_r_o_u_n_d_i_n_g _t_h_e
       _e_v_a_l_u_a_t_i_o_n _o_f _t_h_e _i_n_s_t_a_n_c_e.  There may not be two templates
       which both match the same tree.  [I think it is possible to
       discover this with static analysis of the entire class
       definition lattice.]  [On second thought, this may be
       "halting problem" material, or at least NP-nasty.]

       4.8.6  _C_l_a_s_s__I_n_h_e_r_i_t_a_n_c_e
       Classes automatically inherit properties and methods from
       all superclasses.  Properties which have the same name are
       disambiguated by class name.  Operators with the same name
       must be redefined.  The parent operators may be invoked
       within the rewrite rule via the _s_u_p_e_r=ppppaaaarrrreeeennnntttt keyword.

       4.8.6.1  _C_l_a_s_s_:__C_o_m_p_l_e_x__N_u_m_b_e_r
       For example, an abridged object definition for complex
       numbers:

            ( class
                ID=Complex
                superclass=Number
                ( input
                    (type=Number ID=re)
                    (type=Number ID=im)
                )
                / create a Complex number from two Numbers
                ( op name=Complex type=Complex
                    ( template
                        (type=Number ID=input1)
                        (type=Number ID=input2)
                    )
                    ( rewrite
                        (set (output.re, input1))
                        (set (output.im, input2))
                    )
                )
                / decompose a Complex number into its constituent Numbers
                ( op name=Real type=Number
                    ( template
                        ID=output
                        (type=Complex ID=input)
                    )
                    ( rewrite
                        (set (output, input1.re))
                    )
                )

                                  - 17 -



                ( op name=Imag type=Number
                    ( template
                        ID=output
                        (type=Complex ID=input)
                    )
                    ( rewrite
                        (set (output, input1.im))
                    )
                )
                / arithmetic operators
                / C1 + C2 = C1.re + C2.re, C1.im + C2.im
                ( op name=+ type=Number
                    ( template
                        ID=output
                        (type=Complex ID=input1)
                        (type=Complex ID=input2)
                    )
                    ( rewrite
                        (set(output.re,
                            (op name=+
                                (op name=Real(input1))
                                (op name=Real(input2))
                            )
                        ))
                        (set(output.im,
                            (op name=+
                                (op name=Imag(input1))
                                (op name=Imag(input2))
                            )
                        ))
                    )
                )
                /  C1 - C2 = C1.re - C2.re, C1.im - C2.im
                /  elided for brevity

                           - 33 -

































































                           - 34 -



8.  _P_r_i_m_i_t_i_v_e__C_l_a_s_s__L_i_b_r_a_r_y

This is the first cut at basic tools I think I want for
doing graphics work.  It is in an extremely condensed
pidgin.  These are all built-in classes and methods, library
classes are listed in the next section.


/ Root object
(class
    ID=Object
)


/ Number class
(class
    ID=Number
    super=Object

    / multi ops
    op Self +(Self, Self, multi Self)
    op Self *(Self, Self, multi Self)
    / binary
    op Self -(Self, Self)
    op Self /(Self, Self)
    / unary ops
    op Self -(Self)
    op Self sqrt(Self)
    op Self number(Boolean)
    / multi ops IS THIS THE RIGHT WAY TO DO THIS?
    / assignment op
    op Self Set(Self)
)

/ Angle definition -
/   Number modular around circle
/   Uses signed 2's complement arithmetic to implement clean
/   angular arithmetic.  Going beyond 360 degrees rounds off
/   to beginning.  If these are implemented with signed chars,
/   all trig becomes table lookups.  Should complex numbers
/   subclass from Number or Angle?

(class
    ID=Angle
    super=Number
)
    / get Graphics Gems book and figure out ops
    / probably nothing needs to be overidden from Number

/ Point class
(class











                           - 35 -



    ID=Point
    super=Number

    / creation op
    Point op Point(Number, Number, Number)
    / destruction ops
    Number op X(Point)
    Number op Y(Point)
    Number op Z(Point)
    / binary ops
    Point op +(Point, Point)
    Point op -(Point, Point)
    Point op *(Point, Number)
    Point op *(Number, Point)
    Point op *(Point, Matrix)
    Point op *(Matrix, Point)
    Point op Distance(Point, Point)
    / unary ops
    Point op -(Point)
    Point op sqrt(Point)
    Point op normalize(Point)
    Point op +(Point, Point, multi Point)
)


/ Matrix class - 4x4 matrix for general 3-space xlations
/ Do quaternions completely supercede this?
( class
    ID=Matrix
    super=Number

    / creation op
    Matrix op Matrix(Number, Number, Number, ..., Number)   / 16
    Matrix op Matrix(Point, Point, Point, Point)        / 4x3
    / binary ops
    Matrix op *(Matrix, Matrix)
    / unary ops
    Matrix op invert(Matrix)
    Number op determinant(Matrix)
    Matrix op normalize(Matrix)
    Matrix op transpose(Matrix)
)

/ random numbers.  Deliver a number between 0 & 1.
( class
    ID=Random
    super=Number
)
/ builtins: all the generators I can get with different distributions.
/ Raid Knuth for algorithms.












                           - 36 -



/ Range class
/ A range is a pair of numbers.  The first must be lower than the second.
(class
    ID=Range
    super=Number

    / creation op
    Range op Range(Number, Number)
    / destruction ops
    Number op Lower(Range)
    Number op Upper(Range)
    / binary ops
    / Range op +(Range, Range)  / do these make sense?
    / Range op -(Range, Range)
    Range op Shift(Range, Number)   / shift range up or down
    Range op Scale(Range, Number)   / expand/contract range
    / in Dataset, shift and expand/contract are 'shift' and 'slide' ops
)


/ Boolean class
(class
    ID=Boolean
    super=Object

    / multi ops
    op and(Boolean, multi Boolean)
    op nor(Boolean, multi Boolean)
    op xor(Boolean, multi Boolean)
    / unary ops
    op Boolean not(Boolean)
    op Boolean boolean(Number)
    op Boolean change(anything) / when input changes, become true
    / assignment op
    op Self Set(Self)
)

/ built-in Booleans
stereo      / system is drawing in stereo mode - rw
left_eye    / system is updating left or right eye - ro
out_of_ram  / running on empty: do something! - ro
input_changed   / an input value to this operator changed - ro
switch1     / supplied hardware or window system
switch2
switch3
switch4

/ Address of a node
/ This class needs to be here to provide a specific type for
/ indirect references to nodes.
(class











                           - 37 -



    ID=Address
    super=Object
)


/ Error class: error exception handler
( class
    ID=Error
    super=Object

    / On error #N, execute a program
    / Scoped for all siblings of this node and their descendants.
    ( Self op Self(Number, Void))       / get error
    ( Self op Self(Number, Void, Void)) / get error with message
    / Should the error number be a property?
    / If not specified, default to all?
    ( Self op Raise(Number))        / make error
    ( Self op Raise(Number, Void))      / make error with message
)


/ Void object
/ Various miscellaneous uses : rename it Glue? Clump?
(class
    ID=Void
    super=Object
    (property       // call all inputs in order, or simultaneously?
        ID=ordered
        type=Boolean
        inherited=False
    )
    (property       // when to execute
        ID=execute
        type=Boolean
    )
    (property       // copy tree or evaluate tree and copy value
        ID=evaluate
        type=Boolean
    )
    / clump of nodes
    (op Void call( multi type=anything ))       / do all
    / conditional
    (op Void cond( Boolean, type=anything, type=anything))  / if then else

    / tree surgery operation- can only rearrange at void "cut-points"
    / replace tree at address with tree void
    (op Void replace( Address type=Void), Void)
    / add tree to Void call op: add to collection
    (op Void add( Address(call) type=Void), Void)
    / maybe remove the most recently added tree?












                           - 38 -



    / top of World
    (op Void World( Void))  / top of world - visibility box

    / This is very goofy.  I don't like what it does to
    / tree storage at all.
    / copy value of property from address to address
    (op Void Setprop( Address (property name=xxx),
        Address (property name=xxx) )
    / copy values of all properties from address to address
    (op Void Setprop( Address (property name=xxx),
        Address (property name=xxx) )
)


/ Unknown class
/ internal data of unknown format
/ used for things like network addresses, etc.
/ not manipulable, just there.
( class
    ID=Unknown
    super=Object
)




/ Dataset class
/ data array abstract superclass
(class
    ID=Dataset
    super=Object
    (property
        ID=dimensions
        type=Number
    )
    (property
        ID=indexable
        type=Boolean
    )
    (property
        ID=fractional
        type=Boolean
    )
    / OR
    /(property
    /   ID=indexing
    /   type=Enum(none,integer,fractional)
    /)
    / series of ranges for each dimension
    (property
        ID=infinite











                           - 39 -



        type=Boolean
    )
    (property
        ID=range0
        type=Range
    )

    / type of data held
    (property
        ID=datatype
        type=Address
    )
    / shift data up or down by factors
    (op Self Shift(Self, Number, ...))
    / stretch or shrink indices by scale factors
    (op Self Scale(Self, Number, ...))

    / concatenate two datasets to create a new one
    / they must have the same dimensionality, ranges, & types
    (op Self concat(Self, Self))
)

/ real datasets you can use

/ HDF scientific data set - NCSA HDF format - or abstract superclass as
/ is deemed appropriate by sci-vis people.
/
/ I have the HDF spec but haven't studied it much.
( class
    ID=HDF
    super=dataset
)

/ linear numerical set
( class
    ID=Linear   / spectrum? 1D?
    super=Dataset
)

/ random numbers?  I don't get it!
/ ( class
/   ID=Random
/   super=Linear
/ )

/ Array
/ 2D or 3D array of equally spaced data points
/ may be formulaically derived (infinite=True).  Fractionally indexable
/ (usually).
( class
    ID=Texture











                           - 40 -



    super=Dataset
    (property
        ID=indexable
        type=Boolean
        value=True
    )
)

/ bitmap - 2D monochrome Texture
( class
    ID=Bitmap
    super=Texture
    ( property
        ID=Dimension
        type=Number
        value=2
    )
    ( property
        ID=Size
        type=Box
    )
)

/ pixmap - 2D color Texture
( class
    ID=Pixmap
    super=Texture
    ( property
        ID=Dimension
        type=Number
        value=2
    )
    ( property
        ID=Size
        type=Box
    )
)

/ body - 3D color Texture - throughcut woodgrain etc.
/ I've forgotten the special name for this, if there was one
( class
    ID=Body
    super=Texture
    ( property
        ID=Dimension
        type=Number
        value=3
    )
)

/ Drawable object











                           - 41 -



/ visible screen object abstract superclass
(class
    ID=Drawable
    / for now, all the graphics you get.
    (property
        ID=color
        type=Point
    )
    / used for selecting several representations based on screen size
    / (that is, distance from user)
    / If this property is set, it overrides 3D placement stuff below.
    / If not set, it reflects the 3D placement stuff below.
    (property
        ID=screenbox
        type=Box
    )
    / when is this object to be drawn?
    (property
        ID=execute
        type=Boolean
    )

    / coordinate frame.
    / I thought I was using quaternions?  Boy, am I confused.
    (Property
        ID=frame
        Type=Point
    )

    / xlate, scale, rotate operations
    (op Self Scale(Self, Number X, Y, Z))
    (op Self Xlate(Self, Number X, Y, Z))
    (op Self Rotate(Self, Point Center, ???))

    / collection of drawables, inherit props from here
    (op Drawable call(Drawable, multi Drawable))
    / should be drawable?
)

/ Line
( class
    ID=Line
    Super=Drawable

    (Self op Self(Point, Point))    / two endpoints
    / Connect creates a line vertex
    (Self op Vertex(Point, Point))  / connector: allow painted textures

)
/ Triangle
( class











                           - 42 -



    ID=Triangle
    Super=Drawable

    (Self op Self(Point, Point, Point)) / three endpoints
    / Two triangles connect via a hinge
    (op Self Hinge (Point, Point))      / Allow spray-painted textures
    / should hinge be self or void?
    / hinge will usually use pointers

)

/ Circle
( class
    ID=Circle
    Super=Drawable

    (Self op Self(Point, Number))   / Center, radius
    / does connecting a circle make sense?  At given points?
)

/ Sphere
( class
    ID=Line
    Super=Drawable

    (Self op Self(Point, Number))   / Center, radius
    / does connecting a sphere make sense?  At given points?
)

/ Don't hold your breath waiting for support for the following...
/ Patch
/ ( class
/   ID=Patch
/   Super=Drawable
/
/   / hellifino
/ )

/ Patch:Bezier
( class
/   ID=Bezier
/   Super=Patch
/
/   / hellifino
/ )
/ Quadric
/ ( class
/   ID=Quadric
/   Super=Drawable
/
/   (Self op Self())    / Equation inputs











                           - 43 -



/   (Self op Connect()) / Connect not allowed
/ )
/ Superquadric
/ ( class
/   ID=Line
/   Super=Drawable
/
/   (Self op Self())    / equation inputs
/   (Self op Connect()) / Connect not allowed
/ )
/

/ Painted drawable object
/ Overlay 2D or 3D Drawable with 2D or 3D texture

/ Here we have the classic Trouble With Objects: doing a whole damn
/ class definition just to make two different things interact.
( class
    ID=Painted
    Super=Drawable
    Super=Texture

    / is this image sampled or just a flat bitmap?
    / real-time bitmaps will require the Intel DVI stuff or similar.
    / flat bitmaps are useful for hypertext
    / This can also be stroked Hershey fonts.
    ( property
        ID=flat
        type=Boolean
    )

    (op Apply(Texture, Drawable))
)

/ Built-in textures are 2D: granite, 3D: wood.
/ The apply operator re-runs the texturing operation with a new random
/ seed, to get a new texture.

/ Physical object
/ bounding-box physics abstract superclass.
(class
    ID=Physical
    super=Object
    / motion
    (property
        ID=direction
        type=Point
    )
    (property
        ID=force
        type=Number











                           - 44 -



    )
    / spin
    (property
        ID=rotation_axis
        type=Point
    )
    (property
        ID=angular_momentum
        type=Number
    )
)


// Box definition - used for physical and screen bounding boxes
(class
    ID=Box
    input Point lower, upper
    (op Point ID=Lower(Box))
    (op Point ID=Upper(Box))
    (op Number ID=MinDist(Box))
    (op Number ID=MaxDist(Box))
)


/ Quaternion class
/ used in 3D rotation & placement work
(class
    ID=Quaternion
    super=Number

    / creation op
    Quaternion op Quaternion(Number, Number, Number, Number)
    / destruction ops
    Number op X(Quaternion)
    Number op I(Quaterion)
    Number op J(Quaterion)
    Number op K(Quaterion)
    / binary ops
    / go get the book, I don't know about these operations
    Quaterion op +(Quaterion, Quaterion)
    Quaterion op -(Quaterion, Quaterion)
    Quaterion op *(Quaterion, Number)
    Quaterion op *(Number, Quaterion)
    Quaterion op *(Quaterion, Matrix)
    Quaterion op *(Matrix, Quaterion)
    Quaterion op Distance(Quaterion, Quaterion)
    / unary ops
    Quaterion op -(Quaterion)
    Quaterion op sqrt(Quaterion)
    Quaterion op normalize(Quaterion)
)











                           - 45 -



/ I/O port abstract superclass
( class
    ID=IO
    super=Object

    ( property
        ID=readable
        Type=Boolean
    )

    ( property
        ID=writeable
        Type=Boolean
    )

    ( property
        ID=evaluate
        type=Boolean
    )

    ( Self op Self )

    / notification op to alert handler
    ( Boolean op New (Self))
)

/ MIDI I/O port class- superclass only?  It seems to be useless by itself.
( class
    ID=MidiPort
    Super=IO
    readable=True
    writeable=True
)

/ Speaker I/O port class- superclass only?  It seems to be useless by itself.
/ Not a loudspeaker, but a separate abstract noise-making entity.
( class
    ID=SoundChannel
    Super=IO

    ( property
        ID=Position
        Type=Point
    )
    ( property
        ID=Volume
        Type=Number
    )
)

/ Absolute one-directional input from 0 to 1











                           - 46 -



/ A Slider itself is a number, but it inherits the New
/ An analog joystick is two Sliders.
( class
    ID=Slider
    Super=IO
    Super=Number

    readable=True
    writeable=False

    (Number op Value(Self))
)

/ Relative one-directional input from 0 to 1
/ A Delta itself is a number, but it inherits the New
/ A mouse is two Deltas.
/ An Nintendo joystick is two Deltas, using relative motion and an
/ auto-acceleration input.
( class
    ID=Delta
    Super=IO
    Super=Number

    readable=True
    writeable=False

    (Number op Value(Self))
)

/ Switch
( class
    ID=Switch
    Super=IO
    Super=Boolean
    readable=True
    writeable=False

    (Boolean op Value(Self))
)


/ sound bite
( class
    ID=SoundSample
    super=Linear
    super=SoundChannel

    (op Play(SoundSample, Speaker))
    (op Record(Speaker, SoundSample))
    / the use of the when-executed property to start and stop is a hack
)











                           - 47 -



/ sound synthesizer patch: hardware-dependent.
/ With Csound, an LPC parameter set.
( class
    ID=SoundPatch
    super=Linear
    super=SoundChannel

    (op Play(SoundPatch, Speaker))
    / the use of the when-executed property to start and stop is a hack
)

/ MIDI sound file
( class
    ID=MidiSeq
    super=Dataset
    super=MidiPort

    / one dimension, indexable
    (op Play(MidiSeq, MidiPort))    / play Midi sequence out
    (op Record(MidiPort, MidiSeq))  / real-time capture?  good trick!
    / the use of the when-executed property to start and stop is a hack
)

/ Network port abstract superclass
( class
    ID=Network
    super=Object

    / This port has a unique channel number within the deck
    ( property
        ID=Channel
        type=Number
        writeable=False
    )
    / This protocol has guaranteed delivery
    ( property
        ID=Reliable
        type=Boolean
        writeable=False
    )
    / This protocol has ordered delivery
    ( property
        ID=Ordered
        type=Boolean
        writeable=False
    )

    / constructor & destructor ops
    / A network port's children are the most recent
    / incoming and outgoing trees which went across the net.
    / Void nodes are used as compartmental "cut-points".











                           - 48 -



    ( Self op Self (Void outgoing, incoming))
    ( Self op In (Self))
    ( Self op Out (Self))

    / send & receive programs
    / usually, the port is accessed via a Refer node
    ( Void op Send (Self, Void))
    ( Void op Receive (Self, Void))

    / notification op to alert handler
    ( Boolean op New (Self))
)

/ Virtual circuit port abstract superclass
( class
    ID=VirtualCircuit
    super=Network

    / Inherit channel number
    / This port initiates or accepts connections
    ( property
        ID=Initiate
        type=Boolean
        writeable=False
    )
)

/ Datagram port abstract superclass
( class
    ID=Datagram
    super=Network

)

/ TCP/IP UDP network port
/ 5D program directly in UDP packet, no intermediate protocol layer
/ A channel number is a UDP port number.  It is assigned by the deck
/ when the program is digested.  The deck must upload the tree with
/ the network object to an application to inform the application what
/ the subsidiary port number is.
( class
    ID=UDP
    super=Datagram
    / other host IP & Port number
    ( property
        ID=OtherIP
        type=Unknown        / magic secret data type
        / value will be a text string, with format for RFC xxx
        / proto-assigner
    )
)











                           - 49 -



/ TCP/IP TCP network port
/ 1 port # per channel
( class
    ID=TCP
    super=Network
    / other host IP & Port number
    ( property
        ID=OtherIP
        type=Unknown        / magic secret data type
        / value will be a text string, with format for RFC xxx
        / proto-assigner
    )
)











































































                                  - 18 -



                /  C1 * C2 = (C1.re * C2.re) - (C1.im * C2.im),
                             (C1.re * C2.im) + (C2.re * C1.im),
                ( op name=* type=Number
                    ( template
                        ID=output
                        (type=Complex ID=input1)
                        (type=Complex ID=input2)
                    )
                    ( rewrite
                        (set(output.re,
                            (op name=-
                                (op name=*
                                    (op name=Real(input1))
                                    (op name=Real(input2))
                                )
                                (op name=*
                                    (op name=Imag(input1))
                                    (op name=Imag(input2))
                                )
                            )
                        ))
                        (set(output.im,
                            (op name=+
                                (op name=*
                                    (op name=Real(input1))
                                    (op name=Imag(input2))
                                )
                                (op name=*
                                    (op name=Imag(input1))
                                    (op name=Real(input2))
                                )
                            )
                        ))
                    )
                )
                / Square(Complex input) -> *(input, input)
                ( op name=Square type=Complex
                    ( template
                        ID=output
                        (type=Complex ID=input)
                    )
                    ( rewrite
                        (set (output,
                            (op name=*
                                (input)
                                (input)
                            )
                        ))
                    )
                )
            )











                                  - 19 -



       The Complex object contains two numbers, and implements
       complex arithmetic.  Complex subclasses from Number, because
       it must be able to rewrite itself into Number objects.
       Square rewrites itself into Complex, while all the other
       operators rewrite themselves into Complex or Number.
       Complex objects must be rewritten into Numbers before their
       components may be accessed.  Thus, we can be sure that all
       invocations of Complex are eventually rewritten into Number,
       a primitive class.

       Note that the definitions for addition and subtraction are
       redundant.  The input declaration section says that a
       Complex is an aggregation of two Numbers, in order.  The
       operator inheritance mechanism interacts with this
       declaration to automatically derive the addition and
       subtraction operators defined above.

       The 5D system generates an arithmetic tree of primitive
       objects working from the template patterns in user-defined
       objects in an iterative algorithm.  The program tree

           Complex C1, C2, C3
           label: Real(plus(C3, plus(C1, C2)))
           Imag(label ^)
       generates the two Numbers

           Real(plus(Real(C3), plus(Real(C1), Real(C2))))
           Imag(plus(Imag(C3), plus(Imag(C1), Imag(C2))))
       which may be fed into I/O operations at the top of the
       lattice.

       4.8.7  _D_r_a_w_a_b_l_e__O_b_j_e_c_t_s
       The above classes only implement numerical operations.  The
       Drawable class possesses visual properties such as color and
       position.  The position property is a Point.  The color
       property is a Point in RGB color space.  A property may be
       an object, or a arithmetic tree of objects.  Property
       objects can have no properties themselves.

       The Triangle is a built-in object subclassed off of
       Drawable.  It consists of three Points.  Since a Point is
       composed of three Numbers, a Triangle may have nine
       arithmetic trees underneath it, and constantly change shape
       as those subtrees change value.  A 3D modelling program
       might use this to rubber-band changes in a 3D shape in
       response to numerical input devices, or use feedback to
       implement jiggly objects.















                                  - 20 -



       4.9  _P_r_o_g_r_a_m__I_D__S_c_o_p_i_n_g

       The visibility of IDs is scoped two ways in program trees:
       by tree structure, and by program source.

       4.9.1  _T_r_e_e_-_s_t_r_u_c_t_u_r_e_d__s_c_o_p_i_n_g
       Outside of a class definition, the ID of a node is visible
       to a node's siblings and their children.  Thus,

       Inside a class definition, things are different:  the inputs
       and outputs of the object have special IDs, and IDs declared
       in a method's template are visible within that method's
       rewrite rule.  This allows the template to describe a
       complex tree, and the rewrite rule to tear it apart and
       restructure it.

       4.9.2  _P_r_o_g_r_a_m_-_s_o_u_r_c_e__s_c_o_p_i_n_g
       Different sub-trees in the same scene can be downloaded over
       the network from different applications.  If there were just
       one tree-scoped ID name space, there would be severe
       problems with different programs innocently (or maliciously)
       affecting each other's scene members.  Thus, ID names are
       also "sealed off" for each program source.  A sub-program
       from a different network source may only refer to nodes
       downloaded from that network source, and the primitive
       objects.  A redefinition of a primitive object is also
       visible, since it is referred to by the name of a primitive
       object.

       A parent node may use relative ID addressing to walk a tree
       down to a child node received over the network.  This is
       only a feasible coding technique if the child tree has been
       "syntax-checked" against a template.

       4.10  _C_l_a_s_s__d_e_f_i_n_i_t_i_o_n__s_c_o_p_i_n_g

       A class definition occurs under a program tree node.  Thus,
       it is only available under that parent node.  Two
       definitions of the same class may not be siblings.  However,
       a class may be redefined in a child tree.  The class
       redefinition may only have one superclass, the parent
       definition.  The redefinition may add, delete, or change
       operators or properties.  The parent's version of overridden
       operators may be invoked within more elaborate
       implementations.  For example, the "hinge" operator which
       connects polygons may be redefined to draw a line along the
       edge of the hinge, by redefining the class Drawable and
       overriding the "hinge" definition.

       In a class definition the operator and property definition
       nodes may use the Type= to select the special IDs Parent or











                                  - 21 -



       Self. In an operator definition, Self indicates that the
       type of an operation is that of the class or of any derived
       subclass.  Examination of the Number and Angle classes shows
       an example of this.  The Number operators are defined as
       type Self.  Since Angle derives from Number, all the
       operators from Number simply appear as "Angle + Angle is
       Angle" etc.  without being respecified in the Angle class
       definition.

       Scoping describes which other objects an object definition
       may refer to.  There are four forms of references: rewrite,
       aggregation, data, and property.  Here are the scoping rules
       for each type of reference:

       4.10.1  _R_e_w_r_i_t_e__S_c_o_p_i_n_g
       Rewrite reference scoping controls what a method definition
       can rewrite itself into.  The example class Complex rewrites
       itself into Complex or Number.  Here are the replacement
       scoping rules:

       Self                An object may replace an operation on
                           itself with another expression of its
                           own type.  For instance, Complex
                           replaces the square(Complex) operation
                           with multiply(input1, input1).

       Super               An object may also replace an operation
                           with an expression of its super-class's
                           type, and on up the line to Object.  For
                           instance, Complex replaces the Real and
                           Imag operators with expressions of type
                           Number.  Complex cannot replace any
                           invocations with operators of type
                           Object, because Object has no operators.

       Obviously, if a class can rewrite itself into any other
       class, a circular definition would cause an operation to be
       rewritten endlessly.  While all such errors can be
       discovered automatically, it is very difficult to remove
       them from a design.  This rewrite policy avoids this problem
       entirely by making it impossible for circular references to
       exist.

       Note: inside a rewrite rule, all known classes may be used
       for interior operations. [ I think this deserves its own
       heading, but I don't know quite where. ]

       4.10.2  _A_g_g_r_e_g_a_t_e__S_c_o_p_i_n_g
       Aggregation reference scoping controls what objects may be
       input to an operator rule.  Above, Complex accepts Complex
       and Number as input.  Here are the aggregation scoping











                                  - 22 -



       rules:

       Self                An object may have objects of its own
                           type as inputs.  For instance, Complex
                           accepts square(Complex).

       Super               An object may have objects of its
                           various superclasses as inputs.  For
                           instance, the Complex object creation
                           rule accepts two Numbers as inputs and
                           type-casts them into a Complex.

       Sibling             An object may accept _s_i_b_l_i_n_g objects
                           (other objects with the same
                           superclasses) as inputs.

       In rewrite rules, the special type Parent refers to the
       parent class from whom an operator was inherited.  This is
       used in operator re-defines in classes which override a
       parent class of the same name.  It allows invoking the
       parent's operator definition in the middle of the child's
       operator definition.

       These rules are somewhat arbitrary. They force the class
       designer to think through very carefully the objectives of
       the project, and to understand more fully the "Buddha
       Nature" of the class structure.

       4.10.3  _D_a_t_a__S_c_o_p_i_n_g
       Each object defined in a Data sections of a class must have
       an ID which starts with a $ sign.  References to ID's
       starting with $ sign are scoped to within the class
       definition.  [ This is non-orthogonal with the rest of the
       scoping rules.  Do it some other way.  Maybe myclass::ID? ]

       4.10.4  _P_r_o_p_e_r_t_y__S_c_o_p_i_n_g

       4.10.4.1  _P_r_o_p_e_r_t_y__N_a_m_e_s
       Properties are not subject to a unique name space.
       Different classes may use the same name to define properties
       unique to themselves.  If two different classes both define
       a property and are combined to derive a subclass, the two
       different properties may be disambiguated by the
       _s_u_p_e_r=ppppaaaarrrreeeennnntttt keyword.  The data section of a class
       definition is private; the properties of aggregated data
       types are not available.

       4.10.4.2  _P_r_o_p_e_r_t_y__T_y_p_e_s
       Properties may be of any type which has no properties.  The
       issue here is that if a property can have a property, then
       it can go into a loop attempting to evaluate the original
       property.  Properties are second class citizens in 5D.  They










                                  - 23 -



       are intended as simple adornments directing the evaluation
       of real tree nodes. If a property has important information
       to contribute to the execution of a program, it should be a
       real tree node instead.

       To enforce language simplicity, types of properties may be
       restricted to something.  The siblings of a superclass might
       work out, as might a special sub-tree of simple types in the
       core class hierarchy.

       4.10.4.3  _P_r_o_p_e_r_t_y__I_n_h_e_r_i_t_a_n_c_e
       Properties are inherited dynamically, not statically.  When
       trees are executed via pointers, they inherit their
       properties from the pointing node, not via their original
       parent.

       4.10.5  _A_d_d_r_e_s_s_i_n_g__i_s_s_u_e_s
       Suppose that sender A creates a tree that accepts data from
       sender B. B's data may only appear under A's world according
       to A's wishes.  A may not remove B's data directly, _s_i_n_c_e _i_t
       _c_a_n_n_o_t _a_d_d_r_e_s_s _i_t.  However, A must instead remove A's trees
       which hold B's data.

       This example brings up another point:  dynamic references to
       a non-existent ID are a run-time error.  The Exception class
       handles this type of problem.  The extant expection handler
       receives the code for a non-existent ID reference, and acts
       appropriately.  Static references are not an error.  That
       is, the disappearance of a named node does not automatically
       cause exceptions for all the nodes pointing to it.  A new
       version of the node, or another node somewhere else with the
       same ID, may be interposed without mishap.  A remote
       application which performs this sort of skullduggery should
       put execution interlocks in place beforehand.

       Program references may use IDs with relative indexing:  an
       ID may be followed by zero or more /_n_u_m_b_e_r strings, each
       number an index at successive levels of the tree.  Relative
       indexing only goes down the tree, and ignores network
       scoping rule.  Thus, a program may accept a network packet
       and peer at its contents.  It also allows a complex
       polyhedron to avoid giving an ID to each component when
       specifying interconnections, thus saving much space in
       transmission.

       4.10.6  _A_d_d_r_e_s_s_i_n_g__U_s_e_s
       The ID space is segmented for various "control" trees.  For
       example, one small range of IDs is used inside tree
       definitions to refer to the inputs of that tree.  Another
       range of IDs is used to indicate shared-memory bitmaps for
       concurrent access by 5D and a 2D imaging system (X,











                                  - 24 -



       PostScript, video) on the same machine.


       5.  _L_a_n_g_u_a_g_e__I_m_p_l_e_m_e_n_t_a_t_i_o_n__A_r_c_h_i_t_e_c_t_u_r_e

       5D may be fully interpreted, not that you'd want to.  A full
       interpreter can not build a sortable polygon database, and
       thus cannot implement hidden surfaces.  It would also be
       very slow.  A partial interpreter can build a polygon
       database. This technique analyzes the world description tree
       and decomposes it into jobs to be done at different times.
       The section below describes this technique in more detail.

       The language is also intended to be "hot compiled", that is,
       the deck software can analyze a tree and generate binary
       code to implement that tree.  If it creates nothing more
       than a string of subroutine calls to the op-code handlers of
       the interpreter, it still dissolves away the interpretive
       loop.  A compiler can optimize different built-in types;
       i.e. it can do constant folding for matric operations for
       which portions of a matrix are known.  5D is also targeted
       for ease of compilation on parallel processors.  The
       language attempts to minimize interactions between nodes.  [
       This will require much analysis by experts in parallel
       software. ]

       5.1  _L_a_n_g_u_a_g_e__d_e_s_i_g_n__i_s_s_u_e_s

       5D is intended as a basis for real-time simulation.  As
       such, the power and elegance of abstract research languages
       is unfortunately not available.  Languages such as
       Smalltalk, Prolog, Actor, etc.  are beautifully simple and
       dense, but require unpredictable amounts of CPU time to
       implement their constructs.  5D's language constructs must
       be implementable in a predictable manner.  Every operation
       must require O(1) amount of time to execute.

       5D is designed to be efficient in the amount of space used
       to store 5D programs, and thus efficent in network
       transmission time.  It is also designed to be efficient to
       execute compiled or digested 5D code.  After the simulation
       clock starts, 5D must keep the beat.  Slow digestion of 5D
       code, and the prodigious use of RAM to store pre-computed
       data, is unfortunate but necessary.

       Also, real-time predictability outvotes run-time efficiency.
       For example, whether it would be more efficient to use
       garbage collection rather than freeing memory on the fly is
       immaterial.  The screen cannot stop updating at random
       intervals to do a GC sweep.












                                  - 25 -



       5.2  _L_o_w_-_e_n_d__s_y_s_t_e_m__i_m_p_l_e_m_e_n_t_a_t_i_o_n__s_t_r_a_t_e_g_y

       5D is targeted initially at low-MIPS desktop computers such
       as the 386 PC and the Mac.  A single-CPU frame buffer-based
       computer will implement 5D as a classic simulation system.
       A multi-tasking co-routine package supports a variety of
       subsystems which implement different aspects of the deck:
       sound I/O, positional input devices, force-feedback events,
       network I/O, and last but not least, screen update.  These
       subsystems sleep on different events:  I/O interrupts,
       timeouts, and software-defined events.  Each subsystem
       maintains a task list.  It sleeps on one or more events and
       does a task list each time that event occurs.  The network
       I/O system accepts trees from outside and adds them to the
       world tree.  Each subsystem must be able to insert new tasks
       and delete old tasks on the fly, in response to dynamic
       editing of the tree.

       The polygon database has 2 levels:

          +o a list of high-level objects which can change their
            relative distances and orientations,

          +o where each object is solid and does not change shape.

       The high-level list must be sorted for each mono or stereo
       screen refresh.  Each static object is stored in a Binary
       Space Partition database [ ref ].  (The BSP algorithm does a
       large majority of the polygon sorting work independent of
       the viewpoint.  Animating a static object consists of pre-
       sorting it, then walking the last mile over and over, thus
       considerably speeding up screen refreshes.)  Each screen
       refresh must sort the list of high-level objects in 3-space
       (probably by bounding boxes), and do a fast BSP viewpoint of
       the polygons in each static object.  Depending on the screen
       size and scene complexity, object-first or scan-line-first
       rendering may be appropriate, and the renderer may want to
       switch between them dynamically.  For stereo rendering it
       may make sense to walk through the database rendering both
       screens, or to walk through it twice doing one screen at a
       time.

       Practical experience [ref: Graphics Interface '90, "The
       DataPaper", Green & Shaw] shows that applying BSP to a
       completely static scene winds up fracturing the scene into
       an immense number of polygons, and in fact the 2-level
       scheme ("clumpy BSP?") is preferable in this case also.

       In any event, the Graphics Gems software distribution and
       the VOGLE portable 3D library will provide the source code
       for the first pass at a renderer.











                                  - 26 -



       5.2.1  _S_t_a_t_e__V_e_c_t_o_r_s
       For debugging worlds, and doing animation, it is necessary
       to maintain a state vector of the execution of a world.
       Network control can stop and start execution, and "play" the
       sequence of frames forward and back.

       Because tree evaluations are triggered by multiple clocks
       and asynchronous events, there is not one state vector, but
       instead a "time line" of events and state vectors for the
       appropriate tree.  [This is going to be hairy!]  These state
       vectors are accessible to 5D and are used by the World
       Manager to "swap out" world descriptions as the user wanders
       between them.

       5.3  _N_e_t_w_o_r_k__C_o_m_m_u_n_i_c_a_t_i_o_n_s

       A 5D program is read in from a file or a network connection.
       Decks communicate across networks by sending 5D trees.
       Communication circuits are point-to-point in 5D terms but
       may be multi-drop underneath.  That is, it may receive UDP
       broadcasts but only receives from host X under host X's
       connection object.  Thus, it must have a separate UDP
       broadcast connection object for each incoming host.

       When received, a tree may be examined and then executed or
       rejected, or it may just sit in a holding place for
       reference.  The World Manager needs to accept downloaded
       trees and splice them under a "top of world" partition.
       MazeWar merely needs to examine the latest status message
       from all other players.

       Trees are examined with the 5D _t_e_m_p_l_a_t_e facility:  a
       received tree may be checked against a template as a form of
       syntax check.  If it passes the check, the receiving parent
       tree may choose to execute it.  [ We may want to add the
       boolean Authenticated as a property of a received program.
       The receiver can then take various actions if a program did
       not have the right magic encrypted checksum. ]

       Groupware and Cyberspace applications are not well served by
       the common network protocols; 5D may eventually include a
       mutated form of ISIS, IRC, Kerberos, MUD, or all four.  MUD
       would form a nice permanent object repository for 5D, while
       something like the Habitat system could be built running 5D
       over IRC.

       5.3.1  _R_P_C__c_o_m_p_i_l_e_r
       For doing basic application-deck pair applications, a
       library-building compiler like the one SUN distributes with
       NeWS would be very useful.  [ I read about it in a SUN tech
       papers book: I haven't actually used it. ]











                                  - 27 -



       5.3.2  _C_C_K_:__C_y_b_e_r_s_p_a_c_e__C_o_n_s_t_r_u_c_t_i_o_n__K_i_t
       The effort involved in debugging a client-server network
       protocol is surprisingly large; we're going to need a
       protocol design & debug system for doing many-to-many 5D
       network applications.  It should have a method for tracing
       network messages to & from a deck, and stopping & starting
       operations via network control.  ESTELLE [ ref ??? ] is a
       protocol design language used for describing portions of the
       OSI protocol stack. There are ESTELLE simulators; this would
       make a handy addition to the CCK.

       5.3.3  _N_e_t_w_o_r_k__O_b_j_e_c_t
       The Network object is an abstract superclass for defining
       network protocols for use with 5D.  The object has a channel
       number as a property.  Each network connection has a unique
       number.  This number is used to multiplex communications
       between multiple endpoints in the deck to the outside world.
       Whether a network port initiates or receives connections is
       a property, as is whether the protocol uses reliable and
       ordered delivery.

       A networked deck starts up with various tasks such as
       calibrating I/O devices and adjusting speaker volumes.  It
       then starts a program tree whose sole purpose is to open a
       receptive network connection in each protocol the deck
       supports.

       5.3.3.1  _T_C_P_/_U_D_P__n_e_t_w_o_r_k_i_n_g
       5D uses RFC [ XXX ] to dynamically register the well-known
       TCP & UDP port numbers for these main ports.  It can also
       assign channel numbers to subsidiary network sockets
       dynamically.  Any program when creates subsidiary sockets
       with auto-assigned channels must upload the trees with the
       sockets, to find out their protocol port numbers.  A program
       may also pre-assign port numbers and hope it won't clash
       with anything else. This technique must be used in UDP
       broadcast applications like MazeWar, because every deck must
       use the same port number.

       [ A reliable broadcast protocol could be done by relying on
       a main application to ensure that all other decks got your
       message, and simply making sure that the main application
       got it.  This follows the dictum of philosophy of off-
       loading non-interactive work to the application. ]

       5.4  _W_o_r_l_d__M_a_n_a_g_e_r

       The World Manager is just the main 5D application.  It makes
       sub-worlds available to the user.  A static WM is loaded
       from a file and stores one or more sub-worlds in memory.












                                  - 28 -



       5.4.1  _H_a_l_l_w_a_y
       The prototype implementation of the WM is the _H_a_l_l_w_a_y
       (inspired by various "Rooms" systems).  The user moves down
       a hallway of doors. Each door has some label or icon.  The
       user selects the doorknob, label, or icon and pops into that
       world.

       Under file-based 5D, the world is just there in RAM, waiting
       to run.  Under network-based 5D, there is usually a remote
       application program on a computer for each world.  This
       application handles permanent data storage and complex
       calculation work not easily done with 5D.  In general, the
       application communicates asynchronously with the world,
       implementing all synchronous user interface feedback in
       downloaded 5D.

       5.4.2  _N_e_t_w_o_r_k_e_d__W_M
       A dynamic networked WM downloads world trees across the
       network from a remote master program for this deck.

       In the Hallway, selecting the doorknob causes your WM to
       send a message to the master, which then fires up the
       program for your selected world.  The program contacts your
       WM and downloads the world tree.  The WM accepts the world,
       stuffs it under a "top-of-world" (class Void) node, and
       turns it on.

       When you exit the world, the WM can destroy it or keep it
       around.  The WM can manage memory usage by uploading the
       current state of a world to its counterpart and deleting it.
       When you want to re-enter it, the WM downloads it again.
       Before this, the WM may "swap out" your previous world.

       You may only traverse worlds by passing through the Hallway.
       There's no technical reason for this, it's merely because
       the Hallway's worlds are not conceptually connected.  A
       world may implement its own suite of connected environments
       and traverse them in any order.  A house may have doors,
       windows, ventilator shafts and secret passages for you to
       traverse.


       6.  _T_e_x_t

       5D does not contain a textual abstraction, a font database,
       or support for typewriter keyboards.  There are two possible
       uses for text in 5D:  2-dimensional text and 3-dimensional
       text, with very different aims.  Statistically speaking, 2D
       text is rendered, read, and erased.  3D text, on the other
       hand, tends to be permanent.  It is generally used as a
       label in a larger 3D model.  The low volatility of 3D text











                                  - 29 -



       does not merit devoting scarce permanent deck resources to
       fonts.  It is better handled as a library tree used by
       applications.  2D text is not supported for 2 reasons:

          +o 2D textual graphics has been addressed already by many
            systems: Tex/Dvi, Postscript, troff, the X Window
            System, etc.  Many of these systems have freeware
            versions which could be easily altered to support 2D
            graphics under 5D.  In particular, it would be quite
            easy to create an X window server which moves flat
            bitmaps around in 3-space.  This could be connected to
            5D via 5D networking or by cohabiting in the same
            operating system.  A multi-processor Mach system with
            one CPU running the X stuff and one running 5D would
            make a great hypermedia system.  (Throw another CPU on
            the fire!)

          +o The "official" 5D core language specification only
            supports application features which are widely
            recognized as the one right way to do things, or as one
            of two or three commonly accepted methods.  Text is a
            mess. There are upwards of 20 European Roman-Arabic
            keyboards alone.  Japan has 3 alphabets.  Some
            lettering goes right-to-left, some up-to-down.
            Calligraphic lettering apparently requires an iterative
            method to match up lines between symbols.  We don't
            want to keep adding new text "standards" every six
            months, duplicating the work that's been done for other
            text-processing systems.

       If the specified functionality of a low-end deck ends up
       including a CD-ROM of library materials, the core library
       will include the Hershey fonts, and some basic Adobe-style
       outline fonts, and simple 3D CSG-based text construction
       operators.

       [It might work out for keyboards to just be objects with
       many, many switches.  Another object might interpret these
       into an ASCII dataset, for network communication.]


       7.  _T_e_r_r_a_F_o_r_m_e_r

       The TTTTeeeerrrrrrrraaaaFFFFoooorrrrmmmmeeeerrrr is a visual programming CASE system for 5D
       trees.  It is a 5D program which presents a tree as a 3D
       scene, using translucent structure blocks to display several
       levels of structure simultaneously.  Someday.

       But for now, it's a standard 2D window system application.
       You are able to browse and edit the program tree, and browse
       the class inheritance lattice.  The tree and lattice windows











                                  - 30 -



       use a space-efficient method to display these data
       structures.

       7.1  _T_r_e_e__w_i_n_d_o_w

       The tree window show many levels of a tree, starting at a
       particular node in the tree.  The tree (+ ID=sum (*(1,2),3))
       is shown as:


       ------------------------------------------------------
       | +                                              sum |
       | -------------------------------------------------- |
       | | *                                              | |
       | | ---------------------------------------------- | |
       | | | 1                                          | | |
       | | ---------------------------------------------- | |
       | | ---------------------------------------------- | |
       | | | 2                                          | | |
       | | ---------------------------------------------- | |
       | -------------------------------------------------- |
       | -------------------------------------------------- |
       | | 3                                              | |
       | -------------------------------------------------- |
       ------------------------------------------------------

       This format can not show all the nodes in a 5D program.
       Grasp the edge of a box with the mouse and move it outwards
       to "zoom in" on that box, or move it inwards to move up the
       tree.

       There are two or more tree windows. You may "cut" or "copy"
       a tree in one window, and copy it to the other one.

       If a node has off-screen parents or children, its box is
       drawn differently, alerting you that there is more.

       7.2  _N_o_d_e__W_i_n_d_o_w

       When you select a tree node, you may view that node in full
       in the node window. This window shows all the keywords
       interpreted appropriately, and all extant properties.

       7.3  _T_r_e_e__t_y_p_e_s

       The 5D text format includes the ability to include files.
       These include commands should be preprocessed before a tree
       is downloaded, unless the deck possesses access to a
       universal file name space.













                                  - 31 -



       TF allows you to specify that the contents of a sub-tree
       adhere to a given subset of 5D node types, via the template
       mechanism.  TF saves this non-program information as
       comments in the source, via text comments starting with
       "_F_o_r_m_a_t:", to remember in a later session how you wish to
       view your programs.  It can translate other formats into 5D
       format, allow you to edit the resulting tree, and save it
       out in any format.  Also, if configured correctly, TF can
       invoke an appropriate editor.  You would probably wish to
       use a real 3D modeller to edit a 3D model instead of editing
       the 5D tree; ordinary differential equations are much more
       tractable in the form

                 xxxx'''' ==== xxxx ++++ yyyy
                 yyyy'''' ==== ----xxxx ++++ yyyy
       than as the equivalent 5D format.

       7.4  _C_l_a_s_s__L_a_t_t_i_c_e__B_r_o_w_s_e_r

       You may browse the class inheritance lattice via the class
       browser window.  Of course, you may not edit the class
       inheritance lattice directly.  The lattice is displayed
       using Venn diagram boxes.

       A series of class definitions, where abstract superclasses
       and type-bearing classes are named appropriately:

       (class  ID=abstract1)

       (class  ID=abstract2)

       (class  ID=atype
           super=abstract1
           super=abstract2
       )
       would display in the class lattice browser:


























                                  - 32 -



       ------------------------------------------------------
       | ------------------------------                     |
       | | abstract1                  |                     |
       | |                            |                     |
       | |                            |                     |
       | |                  ------------------------------- |
       | |                  |         |                   | |
       | |                  |  atype  |                   | |
       | |                  |         |                   | |
       | -------------------|----------                   | |
       |                    |                             | |
       |                    |                             | |
       |                    |                   abstract2 | |
       |                    ------------------------------- |
       ------------------------------------------------------


       The browser window cannot display the entire class lattice.
       It does not attempt to show all possible intersections, nor
       even all the intersections of a particular superclass.  If a
       class has any unseen intersections, the border of its box is
       different (monochrome) or its name is in a different color.
       Classes with no on-screen children are not drawn with their
       own box, but if they have children they are underlined or
       drawn in color.  This is simply to avoid screen clutter, or
       "non-data ink".  [ Envisioning Information, Edward Tufte. ]

       To look at all intersections of a superclass, select that
       class.  To select a subset of the intersections of one or
       more classes, mouse-down in one intersection box and drag
       the mouse through all intersections in which you are
       interested.  Since this is a Venn diagram, neighboring boxes
       form a simplified Boolean expression.

       7.5  _O_p_e_r_a_t_o_r_s

       The operator menu gives a list of defined operators.  It can
       give a list of all operators, operators unique to one class,
       or multiply defined operators.

       7.6  _A_d_d_r_e_s_s__n_o_d_e_s

       Address nodes are marked, but automatically are drawn in the
       type of the node they point to.

                                  - 50 -

































































                                  - 51 -



       9.  _5_D__L_i_b_r_a_r_y

       Every deck includes a large library of pre-defined trees
       which do a variety of basic operations:  2D bitmaps, text,
       sample objects, colors, & textures, etc.  The library trees
       are assigned a pre-defined block of IDs.  5D program and
       tree authors may always assume these classes are available,
       as well as the primitive class library.  The following trees
       are from the core tree library, and are a sample of simple
       5D tree composition.

       9.0.1  _F_l_o_a_t_i_n_g__P_i_x_m_a_p_
       The Floating Pixmap is a 2D pixmap which should not be sub-
       or super-sampled, and instead should only be seen at a fixed
       size and place.  It sets its 2D bounding box to force this
       to occur.  This might be used for system status messages.


       ( class
           ID='Floating Pixmap'
           super=Painted
           ( method
               name=Float
               ( template
                   (ID=Pix type=Pixmap)
                   (ID=Frame type=Drawable)
                   (ID=Place type=Box)
               )
               ( rewrite
                   type=Void
                   / Set screen box to force placement on screen
                   ( property
                       name=screenbox
                       value=Place
                   )
                   / If the sizes of the pixmap and the frame are
                   / mis-matched, an exception will be raised,
                   / so don't bother checking them here.
                   Apply(Pix, Frame)
               )
           )
       )

       Notes:

          +o Obviously, the Floating Pixmap would only be invoked
            during a screen refresh.  As a defined tree, the
            Floating Pixmap inherits the evaluation frequency
            property at invocation time.  Setting the evaluation
            frequency would make no sense.












                                  - 52 -



          +o The core library is assumed to be pre-loaded in the
            deck, and its members are referred to by standardized
            code numbers.  However, since Floating Pixmaps can be
            described in 5D, they belong in the core library, not
            the language specification.

          +o A fixed-size pixmap will be legible anywhere on the
            screen.  Since its placement is a 2D graphics decision,
            that is left up to the invoker.

       9.0.2  _S_t_e_r_e_o__F_l_o_a_t_i_n_g__P_i_x_m_a_p
       The Stereo Floating Pixmap object uses two instances of the
       Floating Pixmap object to create a stereo image in a fixed
       size and place on the screen.  Random sub- or super-sampling
       the left and right frames of a stereo image would give your
       visual system severe grief, so the Floating Pixmap library
       routine is the appropriate choice.  The stereo input pixmaps
       may be produced with a ray-tracer or stereo video pairs.


       ( class
           ID='Stereo Floating Pixmap'
           super='Floating Pixmap'

           ( method
               name=Float
               ( template
               (ID=PixLeft type=Pixmap)
               (ID=PixRight type=Pixmap)
               (ID=Frame type=Drawable)
               (ID=Place type=Box)
               )
               ( rewrite
                   type=Void
               / Set screen box, which forces placement on screen
               ( property
                   name=screenbox
                   value=Place
               )
               / Type of cond is VOID, so can't do cond(left, pix, pix)
               cond(LeftEye,
                   Apply(PixLeft, Frame),
                   Apply(PixRight, Frame))
               )
           )
       )

       Notes:

          +o The Stereo Floating Pixmap needs two input bitmaps, and
            the size and placement to use for the maps.  It uses











                                  - 53 -



            the intrinsic boolean variable left_eye to decide
            whether to invoke the Floating Pixmap object on the
            left or right eye image.  Again, the object should only
            be invoked during a retrace event.

          +o With video-in-a-window, you could do this with live
            stereo pairs.

       9.0.3  _S_o_u_n_d__s_a_m_p_l_e__a_t_t_a_c_h_e_d__t_o__o_b_j_e_c_t
       This class definition plays a continuously cycled sound
       sample or synthesizer patch.  It adjusts the volume to your
       distance from it.  This is usually part of a larger object.


       ( class
           ID='Positioned Sound'
           super=SoundChannel

           ( property
               name=Volume
               (
                   type=Number
                   distance((property name=Position type=Point),
                       EyePoint type=Point)
               )
           )

           ( property
               name=execute
               value=True
           )

       )

       Notes:

          +o The actual format of sound samples and instrument
            definitions is very deck-dependent.  Low-end PC sound
            boards have a bunch of oscillators.  They allow you to
            set a bunch of registers for instrument X out of 10,
            and then leave it alone.  Higher-end gear requires
            generating sound samples on the fly and feeding them to
            DMA channels.  The very desirable ability to have
            high-level definitions of several simultaneous sound
            channels making iconic sounds (a FWOOOSH when you grab
            something, a TINK when you hit something metal) is thus
            much easier on PC's than workstations.  On the other
            hand, we need to go to more sophisticated hardware to
            get stereo or 3D sound placement.  There has been work
            on doing 2D placement with Midi.  [Computer Music
            Journal, Feb. 1991, pp. 59] Midi I/O is available for











                                  - 54 -



            all desktop PC's; this is an obvious direction for
            research.

       9.0.4  _F_l_i_p_-_F_l_o_p
       The flip-flop uses feedback to create a simple 1-bit memory
       of past inputs.

       9.0.5  _S_o_f_t_w_a_r_e__P_h_a_s_e_-_L_o_c_k_e_d__L_o_o_p
       The phase-locked loop is a key circuit used in interfacing
       analog and digital circuitry.  The Synthesis operating
       system [ref: Columbia University Technical Report] uses a
       software implementation of a PLL as its scheduler.  Software
       PLLs provide a simple, fast system that responds to external
       rhythms.  A software PLL can interface real-time output to a
       user's work rhythm, and gives a powerful tool for making the
       user interface controlled by the user's time sense.

       It should be possible to interface the MIDI ports with the
       software PLL to do interesting drum machine stuff.

       9.0.6  _S_a_m_p_l_e__&__H_o_l_d
       Sample and hold an input value.  Whenever the input switch
       is true, sample the value.  Whenever the input value
       changes, sample the value.  Output the held value on demand.


                 ( class
                     ID='Sample and Hold'
                     super=Number
                     super=Boolean
                     ( data
                         / secret data sampled & held
                         ID=$Sample
                         type=Number
                     )



























                                  - 55 -



                     ( method
                         / grab data when boolean is true,
                         / and when number changes while boolean is true
                         ( template
                             name=Sample
                             type=Number
                             ( name=switch type=Boolean )
                             ( name=input type=Number)
                         )
                         ( rewrite
                             (cond
                                 (and
                                     (switch)
                                     (or
                                         (inputChange(switch))
                                         (inputChange(value))
                                     )
                                 )
                                 (set($Sample, input))
                                 ()  / else do nothing
                             )
                         )
                     )
                     ( method
                         ( template
                             name=Value
                         )
                         ( rewrite
                             type=Number
                             set(output, $Sample)
                         )
                     )
                 )

       The inputChange boolean operation is extremely useful for
       asynchronous operations such as Sample&Hold.  This class
       does not operate continuously, of course, but instead is
       driven by its inherited clock.
























                                  - 56 -



       10.  _5_D__S_a_m_p_l_e__P_r_o_g_r_a_m_s

       The following program is in severely abridged pidgin 5D for
       clarity.  It dates back to before the addition of objects to
       5D, but does give the flavor of 5D programming.

       10.1  _S_o_u_n_d__m_i_x_e_r

       This is a sample 5D program which implements a simple
       digital sound mixer.  It allows the user to record and play
       back 2 sound samples.

       top of world            / visible universe
       (
           / built-in boolean switch1          record channel 1
           / built-in boolean switch2          record channel 2
           / built-in boolean switch3          playback channel 1
           / built-in boolean switch4          playback channel 2
           / built-in boolean switch5          playback both channels
           call [
               property: evaluate when input changes
               evaluate [
                   property: evaluate never
                   dataset sample1 [
                       property: sound sample, 10 seconds long.
                   ]
                   dataset sample2 [
                       property: sound sample, 10 seconds long.
                   ]
               ]
               evalute [
                   property: evaluate in order         / concurrency control
                   conditional [
                       switch1
                       assign [                        / record sample 1
                           sample1
                           microphone
                       ]
                       null
                   ]
                   conditional [
                       switch2
                       assign [                        / play sample 1
                           sound channel 1
                           sample1
                       ]
                       null
                   ]
                   conditional [
                        switch3
                        assign [                       / record sample 2











                                  - 57 -



                            sample2
                            microphone
                        ]
                       null
                   ]
                   conditional [
                   switch4
                   assign [                            / play sample 2
                               sound channel 2
                               sample2
                           ]
                       null
                   ]
                   conditional [
                       switch5
                       evaluate [                      / mix both samples
                           property: evaluate simultaneously
                           assign [
                               sound channel 1
                               sample1
                           ]
                           assign [
                               sound channel 2
                               sample2
                           ]
                       ]
                       null                            / empty function
                   ]
               ]
           ]
       ]

       This example world has no graphics.  Five switches are used,
       one for each possible operation.  The property of sequenced
       evaluation of sub-trees is used to provide concurrency
       control; only one operation at a time may be used.  A tree
       which is never evaluated is used as a data holder for the
       two sound samples.  The following version uses nested
       conditionals:























                                  - 58 -



       top of world
       [
           / built-in boolean switch1;         record channel 1
           / built-in boolean switch2;         record channel 2
           / built-in boolean switch3;         playback channel 1
           / built-in boolean switch4;         playback channel 2
           / built-in boolean switch5;         playback both channels
           evaluate all [
           property: evaluate when input changes
               evaluate [
                   property: evaluate never
                   dataset sample1 [
                       property: sound sample, 10 seconds long.
                   ]
                   dataset sample2 [
                       property: sound sample, 10 seconds long.
                   ]
               ]
               conditional [
                   property: evaluate in order/ concurrency control
                   switch1
                   assign [                            / record sample 1
                       sample1
                       microphone
                   ]
                   conditional [
                       switch2
                       assign [                        / play sample 1
                           sound channel 1
                           sample1
                       ]
                       conditional [
                           switch3
                           assign [                    / record sample 2
                               sample2
                               microphone
                           ]
                           conditional [
                               switch4
                               assign [                / play sample 2
                                   sound channel 2
                                   sample2
                               ]
                               conditional [
                                   switch5
                                   evaluate [          / mix both samples
                                       property: evaluate simultaneously
                                       assign [
                                           sound channel 1
                                           sample1
                                       ]











                                  - 59 -



                                       assign [
                                           sound channel 2
                                           sample2
                                       ]
                                   ]
                                   null / empty tree
                               ]
                           ]
                       ]
                   ]
               ]
           ]
       ]

       Note that the version with nested conditionals still uses
       the sequential evaluation property.  Multi-processor systems
       can evaluate all 3 branches of a conditional expression
       concurrently, being careful that the false leg of the then-
       else pair leaves no permanent side effects.